Inégalité d'Efron-Stein

En théorie des probabilités, l'inégalité d'Efron-Stein permet de borner la variance d'une fonction générale de variables aléatoires indépendantes. Cette inégalité peut être couplée avec d'autres inégalités de concentration classiques, comme l'inégalité de Bienaymé-Tchebychev.

Énoncé

Soient $X_{1},\dots ,X_{n}$ des variables aléatoires indépendantes à valeurs dans un espace ${\mathcal {X}},Z=f(X_{1},\dots ,X_{n})$ une fonction générale des $X_{1},\dots ,X_{n}$ avec $f\colon {\mathcal {X}}^{n}\to \mathbb {R}$ alors

$\mathrm {Var} (Z)\leq \sum _{i=1}^{n}\mathbb {E} \left[(Z-\mathbb {E} ^{(i)}[Z])^{2}\right]$

où $\mathbb {E} ^{(i)}$ désigne l'espérance conditionnelle conditionnée par rapport à $X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i+1},\dots X_{n})$, c'est-à-dire

$\mathbb {E} ^{(i)}Z=\int _{\mathcal {X}}f(X_{1},\dots ,X_{i-1},x,X_{i+1},\dots ,X_{n})\mathrm {d} \mu _{i}(x)$ où $\mu _{i}$ est la densité de $X_{i}$.

Si on pose $X_{1}',\dots ,X_{n}'$ des copies indépendantes des $X_{1},\dots ,X_{n}$ et que l'on pose

$Z_{i}'=f(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n})$,

alors le membre de droite de cette inégalité peut également s'écrire :

$\sum _{i=1}^{n}\mathbb {E} \left[(Z-\mathbb {E} ^{(i)}[Z])^{2}\right]={\frac {1}{2}}\sum _{i=1}^{n}\mathbb {E} \left[(Z-Z_{i}')^{2}\right]=\sum _{i=1}^{n}\mathbb {E} \left[(Z-Z_{i}')_{+}^{2}\right]=\sum _{i=1}^{n}\mathbb {E} \left[(Z-Z_{i}')_{-}^{2}\right]$ où $x_{+}=\max(x,0)$ et $x_{-}=\max(-x,0)$.

On peut également écrire que $\sum _{i=1}^{n}\mathbb {E} \left[(Z-\mathbb {E} ^{(i)}[Z])^{2}\right]=\inf _{Z_{i}}\sum _{i=1}^{n}\mathbb {E} \left[(Z-Z_{i})^{2}\right]$ où l'infimum est pris sur l'ensemble des $X^{(i)}$-mesurable et les variables $Z_{i}$ admettant un moment d'ordre deux.

Démonstration

L'idée de la preuve est de généraliser le cas où quand $Z=X_{1}+\dots +X_{n}$, on a $\mathrm {Var} (Z)=\sum _{i=1}^{n}\mathrm {Var} (X_{i}).$

Si on note $\mathbb {E} _{(i)}$ l'espérance conditionnelle conditionnée par rapport à $(X_{1},\dots ,X_{i})$ (avec la convention $\mathbb {E} _{(0)}=\mathbb {E}$ et que l'on pose

$\forall 1\leq i\leq n,\qquad \Delta _{i}=\mathbb {E} _{(i)}[Z]-\mathbb {E} _{(i-1)}[Z]$

alors $Z-\mathbb {E} [Z]=\sum _{i=1}^{n}\Delta _{i}.$

Donc $\mathrm {Var} (Z)=\mathbb {E} \left[\left(\sum _{i=1}^{n}\Delta _{i}\right)^{2}\right]=\sum _{i=1}^{n}\mathbb {E} [\Delta _{i}^{2}]+2\sum _{i<j}\mathbb {E} [\Delta _{i}\Delta _{j}].$

Or, si $i<j,\mathbb {E} _{(i)}[\Delta _{j}]=\mathbb {E} _{(i)}\left[\mathbb {E} _{(j)}[Z]-\mathbb {E_{(j-1)}} [Z]\right]=\mathbb {E} _{(i)}[Z]-\mathbb {E} _{(i)}[Z]=0$ donc

$\mathbb {E} [\Delta _{i}\Delta _{j}]=\mathbb {E} \left[\mathbb {E} _{(i)}[\Delta _{i}\Delta _{j}]\right]=\mathbb {E} \left[\Delta _{i}\mathbb {E} _{(i)}[\Delta _{j}]\right]=0.$

On a donc à présent que $\mathrm {Var} (Z)=\sum _{i=1}^{n}\mathbb {E} [\Delta _{i}^{2}]$.

D'après le théorème de Fubini, $\mathbb {E} _{(i)}\left[\mathbb {E} ^{(i)}[Z]\right]=\mathbb {E} _{(i-1)}[Z]$, d'où $\Delta _{i}=\mathbb {E} _{(i)}\left[Z-\mathbb {E} ^{(i)}[Z]\right]$. D'après l'inégalité de Jensen,

$\Delta _{i}^{2}=\left(\mathbb {E} _{(i)}\left[Z-\mathbb {E} ^{(i)}[Z]\right]\right)^{2}\leq \mathbb {E} _{(i)}\left[\left(Z-\mathbb {E} ^{(i)}[Z]\right)^{2}\right].$

Finalement, $\mathrm {Var} (Z)=\sum _{i=1}^{n}\mathbb {E} [\Delta _{i}^{2}]\leq \sum _{i=1}^{n}\mathbb {E} \left[\mathbb {E} _{(i)}\left[\left(Z-\mathbb {E} ^{(i)}[Z]\right)^{2}\right]\right]=\sum _{i=1}^{n}\mathbb {E} \left[\left(Z-\mathbb {E} ^{(i)}[Z]\right)^{2}\right]$.

Démontrons maintenant l'égalité des termes pour le membre de droite de l'inégalité d'Efron-Stein. Si on note $\mathrm {Var} ^{(i)}$ la variance conditionnelle conditionnée par rapport à $X^{(i)}$ alors

$\sum _{i=1}^{n}\mathbb {E} \left[(Z-\mathbb {E} ^{(i)}[Z])^{2}\right]=\sum _{i=1}^{n}\mathbb {E} \left[\mathrm {Var} ^{(i)}(Z)\right].$

En utilisant le fait que si $X$ et $Y$ sont des variables aléatoires réelles indépendantes et identiquement distribuées alors $\mathrm {Var} (X)={\frac {1}{2}}\mathbb {E} \left[(X-Y)^{2}\right].$

Or conditionnellement à $X^{(i)}$, les variables $Z$ et $Z_{i}'$ sont indépendantes et identiquement distribuées d'où

$\mathrm {Var} ^{(i)}(Z)={\frac {1}{2}}\mathbb {E} ^{(i)}\left[(Z-Z_{i}')^{2}\right]=\mathbb {E} ^{(i)}\left[(Z-Z_{i}')_{+}^{2}\right]=\mathbb {E} ^{(i)}\left[(Z-Z_{i}')_{-}^{2}\right].$

La dernière égalité vient du fait que l'on puisse écrire que $\mathrm {Var} (X)=\inf _{a\in \mathbb {R} }\mathbb {E} [(X-a)^{2}]$. Donc conditionnellement à $X^{(i)}$, on peut écrire que

$\mathrm {Var} ^{(i)}(Z)=\inf _{Z_{i}}\mathbb {E} ^{(i)}\left[(Z-Z_{i})^{2}\right].$

Applications

Fonctions avec différences bornées

Une fonction $f\colon {\mathcal {X}}^{n}\to \mathbb {R}$ possède la propriété de différences bornées s'il existe des constantes positives $c_{1},\dots ,c_{n}$tels que

$\forall 1\leq i\leq n,\qquad \sup _{x_{1},\dots ,x_{n},x_{i}'\in {\mathcal {X}}}|f(x_{1},\dots ,x_{n})-f(x_{1},\dots ,x_{i-1},x_{i}',x_{i+1},\dots ,x_{n})|\leq c_{i}$

Si une fonction $f$ vérifie cette propriété avec les constantes $c_{1},\dots ,c_{n}$, alors d'après l'inégalité d'Efron-Stein et parce que $\mathrm {Var} ^{(i)}(Z)\leq \mathbb {E} ^{(i)}\left[(Z-Z_{i})^{2}\right]$ pour $Z_{i}={\frac {1}{2}}\left[\sup _{x_{i}'\in {\mathcal {X}}}f(X_{1},\dots ,X_{i-1},x_{i}',X_{i+1},\dots ,X_{n})+\inf _{x_{i}'\in {\mathcal {X}}}f(X_{1},\dots ,X_{i-1},x_{i}',X_{i+1},\dots ,X_{n})\right]$, on a

$\mathrm {Var} (Z)\leq {\frac {1}{4}}\sum _{i=1}^{n}c_{i}^{2}.$

Fonctions auto-bornées

On dit qu'une fonction positive $f:{\mathcal {X}}^{n}\to [0,\infty )$ est auto-bornée s'il existe des fonctions $f_{i}:{\mathcal {X}}^{n-1}\to \mathbb {R}$ tels que pour tout $x_{1},\dots ,x_{n}\in {\mathcal {X}}$ et tout $i=1,\dots ,n$,

$0\leq f(x_{1},\dots ,x_{n})-f_{i}(x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{n})\leq 1$

et

$\sum _{i=1}^{n}(f(x_{1},\dots ,x_{n})-f_{i}(x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{n}))\leq f(x_{1},\dots ,x_{n}).$

D'après l'inégalité d'Efron-Stein, toute fonction $f$ auto-bornée vérifie $\mathrm {Var} (f(X_{1},\dots ,X_{n}))\leq \mathbb {E} [f(X_{1},\dots ,X_{n})]$.